/**
 * 
 */
package string.passed2;

/**
 * @author xyyi
 *
 */
public class ValidPalindrome {

	/**
	Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

	For example,
	"A man, a plan, a canal: Panama" is a palindrome.
	"race a car" is not a palindrome.

	Note:
	Have you consider that the string might be empty? This is a good question to ask during an interview.

	For the purpose of this problem, we define empty string as valid palindrome.
	 */
	public boolean isPalindrome(String s) {
		if (s == null || s.isEmpty()) {
			return true;
		}

		int left = 0;
		int right = s.length() - 1;
		while (left < right) {
			if (!Character.isLetterOrDigit(s.charAt(left))) {
				left++;
			} else if (!Character.isLetterOrDigit(s.charAt(right))) {
				right--;
			} else if (Character.toLowerCase(s.charAt(left)) != Character
					.toLowerCase(s.charAt(right))) {
				return false;
			} else {
				left++;
				right--;
			}
		}

		return true;
	}	
	
	public boolean isPalindrome2(String s) {
		if (s == null) {
			return true;
		}

		// empty string case is covered
		int left = 0, right = s.length() - 1;
		while (left < right) {
			char leftChar = Character.toLowerCase(s.charAt(left));
			if (!Character.isDigit(leftChar) && !Character.isLetter(leftChar)) {
				left++;
				continue;
			}
			char rightChar = Character.toLowerCase(s.charAt(right));
			if (!Character.isDigit(rightChar) && !Character.isLetter(rightChar)) {
				right--;
				continue;
			}
			if (leftChar != rightChar) {
				return false;
			}
			left++;
			right--;
		}

		return true;
	}

    public boolean isPalindrome3(String s) {
        String ss = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        return ss.equals(new StringBuilder(ss).reverse().toString());
    }	
	
	/**
	 * 
	 */
	public ValidPalindrome() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
